package leetcode.leetcode100;

public class longestPalindrome {
    public static void main(String[] args) {
       String s = "cbbd";
        System.out.println(process(s));
    }
    public static String process(String s){
        if (s == null || s.length() == 0){
            return null;
        }
        char[] res = manacherString(s);
        int[] pArr = new int[res.length];//回文半径数组
        int R = -1, C = -1, max = Integer.MIN_VALUE;//R是回文右边界再往右一个位置
        int ans = 0;
        for (int i = 0; i < res.length; i++) {

            pArr[i] = R>i? Math.min(pArr[2 * C - i], R - i) : 1;

            while (i+pArr[i]<res.length && i - pArr[i] > -1){
                if (res[i+pArr[i]]== res[i-pArr[i]]){
                    pArr[i]++;
                }else {
                    break;
                }
            }
            if (i + pArr[i] > R) {
                R = i + pArr[i];
                C = i;
            }
            if (pArr[i]>max){
                max = pArr[i];
                ans = i/2;
            }
        }
        return s.substring(ans-(max-1)/2,ans+max/2);
    }
    public static char[] manacherString(String s){
        char[] str = s.toCharArray();
        char[] chars = new char[s.length()*2+1];
        int cur = 0;
        for (int i = 0; i <chars.length ; i++) {
            if ((i&1)==0){
                chars[i] = '#';
            }else {
                chars[i] = str[cur++];
            }

        }
        return chars;
    }
}
